Recent advances in semiconductor technology have resulted in the development of nonvolatile semiconductor memory. Flash memory is one type of nonvolatile semiconductor memory. Data storage systems (hereafter, referred to as “storage system”) that use flash memory as the storage medium have been developed in recent years.
The characteristics of flash memory (for example, NAND-type flash memory in particular) will be explained next. Flash memory is configured from multiple physical blocks. The physical blocks are configured from multiple physical pages. Flash memory is unable to rewrite data in units of physical pages. Therefore, in a case where the data of a certain physical page is to be rewritten, the following processing is required:
1) Temporarily save data stored in the physical block comprising the rewrite-target physical page to another physical page;
2) Erase all the data from the physical block comprising the rewrite-target physical page; and
3) Write data to the rewrite-target physical page from which the data has been erased.
That is, when rewriting data in a flash memory, data must first be erased. However, it takes longer to erase data from a single physical block of flash memory than it does to write data to a single physical page (for example, roughly an order of magnitude longer). Consequently, a method in which the rewrite data is written to an unused physical page is known.
However, in this case, an unused physical page inside the flash memory is consumed every time a data rewrite occurs. For this reason, in a case where there is a shortage of unused physical pages, an unused physical page must be secured by erasing unneeded data from the flash memory as described hereinbelow. This process is called “reclamation”.
1) Identify an erase-target physical block.
2) Copy valid data stored in the erase-target physical block to a different unused physical page. In accordance with this, the data stored in all of the physical pages of the erase-target physical block become invalid data.
3) Erase all the data in the erase-target physical block.
However, the number of data erases is limited in a flash memory. The upper limit of the number of data erases per physical block will differ in accordance with the type of memory cell of the flash memory, but, for example, is around 100,000 times, and exceeding this upper limit runs the risk of no longer being able to erase data (or, no longer being able to store data for a fixed period of time when storing data in a physical block for which the number of data erases has exceeded the upper limit). For this reason, an “equalization function” for equalizing the erases of the respective physical blocks such that erasing is not focused on a specific physical block is incorporated into the flash memory.
Furthermore, the longer that data is stored in the flash memory, the higher the probability of a read error occurring. This phenomenon is called a “retention error”. To avoid this phenomenon, a “refresh function” for moving the data of a physical page to a different physical page when a fixed period of time has elapsed is incorporated into the flash memory.
These functions, i.e., “reclamation”, the “equalization function” and the “refresh function”, are referred to generically as “wear leveling”.
To realize the various functions incorporated into the above-described flash memory, the flash memory comprises a logical address-physical address translation table, which denotes the corresponding relationship between a logical address and a physical address. A logical address is presented to a higher-level interface, and the flash memory physical address is concealed. Then, a logical address, which has been specified by the higher-level interface, is translated to the corresponding physical address by referencing the logical address-physical address translation table. For example, in a case where the higher-level interface instructs that data “A” be written to a certain logical address “1”, the following processing is executed:
1) Identify an unused physical page “101” of the flash memory;
2) Write the data “A” to the unused physical page “101”;
3) Change the reference destination of the logical address “1” in the logical address-physical address translation table to the physical address of the physical page “101” to which the data was written.
The logical address-physical address translation table is updated each time a data write occurs. That is, since the logical address-physical address translation table is frequently updated, this table is generally deployed and used in the main memory for which access performance is high (high-speed data reads and writes). However, data stored in the main memory is erased when the power to the storage system is shut off. Accordingly, when the storage system power is shut off, the logical address-physical address translation table stored in the main memory must be saved to the flash memory.
As a method for saving the data stored in the main memory to the flash memory at high speed, Patent Literature 1 discloses a method, which uses a high-speed mode for writing only to the least significant bit in a case where the flash memory is a multi-valued memory (MLC (Multi Level Cell)).
Patent Literature 2 discloses a method for storing the logical address-physical address translation table in flash memory the same as user data, and reconstituting the logical address-physical address translation table from the data stored in the flash memory.